package com.tgy.leetcode.binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020/12/27 下午9:45
 * 二叉树遍历
 */
public class BinaryTreeTraversal {

    public static List<Integer> inorderTraversal(TreeNode treeNode){

        ArrayList<Integer> rets = new ArrayList<>();

        if (Objects.isNull(treeNode)) {

            return rets;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = treeNode;
        while (true) {

            while (node != null) {

                rets.add(node.val);
                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            node = stack.pop().right;
        }
        return rets;
    }
    /**
     * 前序非递归遍历
     * @param treeNode
     * @return
     */
    public static List<Integer> inorderTraversal01(TreeNode treeNode){

        ArrayList<Integer> rets = new ArrayList<>();

        if (Objects.isNull(treeNode)) {

            return rets;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = treeNode;
        while (true) {

            while (node != null) {

                rets.add(node.val);
                if (node.right != null) {

                    stack.push(node.right);
                }
                node = node.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            node = stack.pop();
        }
        return rets;
    }

    public static List<Integer> inorderTraversal02(TreeNode treeNode){

        ArrayList<Integer> rets = new ArrayList<>();

        if (Objects.isNull(treeNode)) {

            return rets;
        }

        Stack<TreeNode> stack = new Stack<>();

        stack.push(treeNode);
        TreeNode node;
        while (!stack.isEmpty()) {

            node = stack.pop();
            rets.add(node.val);

            if (node.right != null) {

                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return rets;
    }

    public static List<Integer> postorderTraversal(TreeNode treeNode) {

        ArrayList<Integer> rets = new ArrayList<>();

        if (Objects.isNull(treeNode)) {

            return rets;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);

        TreeNode preVistorNode = null, node = null;

        while (!stack.isEmpty()) {

            node = stack.peek();

            /**
             * 如果node为叶子节点，或者当前节点是前一个遍历节点的父节点
             */
            if ((node.left == null && node.right == null) ||
                (preVistorNode != null && (node.left == preVistorNode || node.right == preVistorNode))) {

                stack.pop();
                preVistorNode = node;
                rets.add(node.val);
            }else {

                if (node.right != null) {

                    stack.push(node.right);
                }

                if (node.left != null) {

                    stack.push(node.left);
                }
            }


        }
        return rets;
    }
    /**
     * 局部前序倒序就是后续
     * @param treeNode
     * @return
     */
    public static List<Integer> postorderTraversal01(TreeNode treeNode) {

        ArrayList<Integer> rets = new ArrayList<>();

        if (Objects.isNull(treeNode)) {

            return rets;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        TreeNode node;

        while (!stack.isEmpty()) {

            node = stack.pop();
            rets.add(0,node.val);

            if (node.left != null) {

                stack.push(node.left);
            }

            if (node.right != null) {

                stack.push(node.right);
            }
        }

        return rets;
    }

    public static List<Integer> preorderTraversal(TreeNode treeNode) {

        List<Integer> rets = new ArrayList<>();

        if (Objects.isNull(treeNode)) {

            return rets;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = treeNode;

        while (true) {

            while (node != null) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                break;
            }

            node = stack.pop();
            rets.add(node.val);
            node = node.right;
        }

        return rets;
    }

    public static List<Integer> leveTraversal(TreeNode treeNode) {

        List<Integer> rets = new ArrayList<>();

        if (Objects.isNull(treeNode)) {

            return rets;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.offer(treeNode);
        TreeNode node;
        int everyleveNum = 1,leveNum = 0;
        while (!queue.isEmpty()) {

            node = queue.poll();

            rets.add(node.val);
            if (node.left != null) {

                queue.offer(node.left);
            }

            if (node.right != null) {

                queue.offer(node.right);
            }

            everyleveNum--;

            if (everyleveNum == 0) {

                leveNum++;
                everyleveNum = queue.size();
            }

        }

        System.out.println("二叉树总共:" + leveNum + "层");

        return rets;
    }
}
